package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/20
 * @description <a href="https://leetcode.cn/problems/sum-of-left-leaves/description/">...</a>
 */
public class Leetcode404_左叶子之和 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用全局变量,记录所有左叶子节点之和
     */
    private int leftSum = 0;

    /**
     * 采用递归算法
     * 采用全局变量,记录左叶子节点之和
     * 对二叉树进行递归前序遍历,在递归函数中传入节点属于左子节点还是右子节点,并在递归过程中,将左子节点的值加入和中
     */
    public int sumOfLeftLeaves(TreeNode root) {
        //边界条件校验
        if (root == null) {
            return 0;
        }

        //调用递归实现
        traversal(root.left, true);
        traversal(root.right, false);

        //返回左叶子节点和
        return leftSum;
    }

    /**
     * 递归实现
     * 遍历二叉树,如果当前节点是左叶子节点,则记录加和
     */
    private void traversal(TreeNode node, boolean left) {
        //递归终止条件
        if (node == null) {
            return;
        }

        //如果当前节点是左叶子节点,则记录加和
        if (node.left == null && node.right == null) {
            if (left) {
                leftSum += node.val;
            }
            return;
        }

        //递归处理左、右子树
        traversal(node.left, true);
        traversal(node.right, false);
    }

}
